package liangzhi;

import java.util.ArrayDeque;
import java.util.Queue;
import java.lang.*;
/**
 * @auther zhouliangliang
 * 生成n层满二叉树
 * @date 2025/5/8 14:54
 * @description
 */
public class GenFullBinaryTree {
    public TreeNode<Integer> genFullBT(int levels, int value) {
        if (levels <= 0 ) {
            return null;
        }
        TreeNode<Integer> root = new TreeNode<>(null);
        root.setData(value++);
        if(levels == 1) {
            return root;
        }

        Queue<TreeNode<Integer>> queue = new ArrayDeque<>();

        queue.add(root);

        int currentLevel = 1;
        int nodeInCurrentLevel = 1;
        int nodeInNextLevel = 0;
        while (currentLevel < levels && ! queue.isEmpty()) {

            TreeNode<Integer> node = queue.poll();
            nodeInCurrentLevel --;


            TreeNode<Integer> left = new TreeNode<>(null);
            left.setData(value++);
            node.setLeft(left);
            queue.add(left);
            nodeInNextLevel ++;

            TreeNode<Integer> right = new TreeNode<>(null);
            right.setData(value++);
            node.setRight(right);
            queue.add(right);
            nodeInNextLevel++;

            if(nodeInCurrentLevel == 0) {
                currentLevel ++;
                nodeInCurrentLevel = nodeInNextLevel;
                nodeInNextLevel = 0;
            }

        }
        return root;
    }

    /**
     * 二叉树层序遍历
     * @param node
     */
    private void printTree(TreeNode<Integer> node) {
        if (null == node) {
            return;
        }

        Queue<TreeNode<Integer>> queue = new ArrayDeque<>();
        queue.add(node);
        printQueue(queue);
    }

    private void printQueue(Queue<TreeNode<Integer>> queue) {
        if(null == queue || queue.isEmpty()) {
            return;
        }
        Queue<TreeNode<Integer>> levelQueue = new ArrayDeque<>();
        StringBuilder builder = new StringBuilder();
        while (!queue.isEmpty()) {
            TreeNode<Integer> current = queue.poll();
            if(null != current.getLeft()) {
                levelQueue.add(current.getLeft());
            }

            if(null != current.getRight()) {
                levelQueue.add(current.getRight());
            }
            builder.append(current.getData() + " ");
        }
        System.out.println(builder.toString());
        printQueue(levelQueue);
    }

    public void visitFourTree(TreeNode<Integer> current) {
        TreeNode<Integer> tmp = current;
        visitTree(current);
        System.out.println("-------------------------------------");
        current = current.getParent();
        while (null != current && current != tmp) {
            visitTree(current);
            current = current.getParent();
            System.out.println("-------------------------------------");
        }
    }

    public void visitTree(TreeNode<Integer> root) {
        if(null == root) {
            return;
        }
        System.out.print(root.getData() + " ");
        visitTree(root.getLeft());
        visitTree(root.getRight());
    }

    public static void main(String[] args) {
        GenFullBinaryTree gbt = new GenFullBinaryTree();
        TreeNode node1 = gbt.genFullBT(4,1);
//        gbt.visitTree(node1);
        TreeNode node2 = gbt.genFullBT(4,16);
        TreeNode node3 = gbt.genFullBT(4,31);
        TreeNode node4 = gbt.genFullBT(4,46);
        node1.setParent(node2);
        node2.setParent(node3);
        node3.setParent(node4);
        node4.setParent(node1);

        gbt.visitFourTree(node1);
    }
}








































